package simple.string;

/**
 * <a href="https://leetcode.cn/problems/valid-palindrome-ii/">680. 验证回文串 II</a>
 * 给你一个字符串 s，最多 可以从中删除一个字符。
 * 请你判断 s 是否能成为回文字符串：如果能，返回 true ；否则，返回 false 。
 * 示例 1：
 *   输入：s = "aba"
 *   输出：true
 * 示例 2：
 *   输入：s = "abca"
 *   输出：true
 *   解释：你可以删除字符 'c' 。
 * 示例 3：
 *   输入：s = "abc"
 *   输出：false
 * 提示：
 *   1 <= s.length <= 10^5
 *   s 由小写英文字母组成
 * @author 刘学松
 * @date 2023-06-19 10:05
 */
public class 验证回文串II {
    public boolean validPalindrome(String s) {
        int low = 0, high = s.length() - 1;
        while (low < high) {
            char c1 = s.charAt(low), c2 = s.charAt(high);
            if (c1 != c2) {
                return subValid(s, low+1, high) || subValid(s, low, high-1);
            } else {
                ++low;
                --high;
            }
        }
        return true;
    }

    public boolean subValid(String s, int low, int high) {
        while (low < high) {
            char c1 = s.charAt(low), c2 = s.charAt(high);
            if (c1 != c2) {
                return false;
            } else {
                ++low;
                --high;
            }
        }
        return true;
    }
}
